1. Field of the Invention
The present invention relates to a disk array controller, and more particularly to a method of generating data by a parity engine in a disk array controller by using map tables.
2. Description of Related Art
As the present information technology advances, data storing and data security become increasingly important, and thus many storage medium related technologies are developed. For example, the input/output (I/O) efficiency of a disk is improved to cope with the increasing demand for a higher performance of a computer system. Another example is that, in addition to the requirement for a larger storage capacity, higher security and reliability are also taken into consideration, and the data access service can be continuously provided even when there is a problem occurred in the hard disk drive.
With the foregoing considerations, the concept of a redundant array of inexpensive/independent disks (RAID) is introduced. The purpose of the RAID resides in storing data into several different disks to improve the storing efficiency and mutually backuping data on multiple disk drives to enhance the reliability of stored data. The advantages of the RAID include providing a better data storage efficiency and a higher data fault tolerance capability. By evenly distributing the workload among several physical disks, a better performance can be achieved. By means of multiple data operations, a high fault tolerance capability can be achieved by rebuilding data through the aid of other disk drives if one or more disk drives or sectors fail.
A disk array is shown as a single logical disk in an operating system. A RAID controller can control how the data is stored and accessed between a physical disk array and a logical disk array, in which several disk drives are integrated into a single virtual disk drive with a large capacity through the RAID controller. The implementation of various different types of the RAID is introduced as follows.
A RAID level 0 (RAID-0) is a faster disk array, in which data is written linearly or through different disk drives to achieve faster data transmission. This technology divides data and stores them into different disk drives for providing the best performance, but having no fault tolerance capability. The RAID level 0 accesses data over several different disk drives. If any one of the disk drives fails, the whole record of data will be damaged or destroyed. Referring to FIG. 1 for the schematic view of the prior art, a complete set of data 10 is divided and computed by the algorithm of the RAID level 0. For example, the data 10 is divided into segments 1, 2, 3, 4, 5, 6 separately, in which the data 1, 3, 5 are stored in a first disk 11 and the data 2, 4, 6 are stored in a second disk 12. The two disk drives 11, 12 jointly access a set of data, and thus the data access rate can be almost doubled.
A RAID level 1 (RAID-1) uses at least two disk drives such as a first disk 11 and a second disk 12 as shown in FIG. 2, and the both disks 11, 12 store the same data block. In other words, two identical sets of data are created in two different disk drives while storing the data 10, and thus the first disk 11 and the second disk 12 simultaneously contain the data 10. If there are data damaged or destroyed in a disk, another one can take over immediately, so that the RAID level 1 has a high reliability and a high fault tolerance capability. However, because it is necessary to duplicate one data set into two disk drives, the performance will be lowered and the cost will be increased.
A RAID level 0+1 (RAID-0+1) integrates the advantages of a high data access rate of the RAID level 0 and a high reliability of the RAID level 1. As shown in FIG. 3, the data 10 is divided into segments 1, 3, 5 and 2,4,6 stored in the first disk 11 and the second disk 12, respectively, and then they are also mapped into another disk drive group 11, 12 to achieve the effect of a high fault tolerance. The data is divided and stored into many disk drives, and each disk drive accompanies another disk drive having the same data, and thus benefiting a fast data access and a high fault tolerance.
With the progress to a RAID level 5 (RAID-5), which provides a better efficiency and a higher fault tolerance capability to a disk array, a set of parity data (which is generally called P value or an XOR parity) is stored in addition to the user data according to its design. The parity data is a calculation result by performing XOR operations to all corresponding user data, and its operational formula is given as follows:P=D0+D1+D2+ . . . +Dn−1  (1)
Where, “+” stands for the XOR operation, P for the parity data, and D0, D2, . . . , Dn−1 for the user data, and n stands for the number of user data disks.
In FIG. 4, four disk drives A, B, C, D are used to form a disk array of RAID level 5. Wherein there are a plurality of strips including a first strip D0 stored in a disk drive A, a second strip D1 stored in a disk drive B, a third strip D2 stored in a disk drive C, a first parity P1 corresponding to strips D0, D1, D2 and stored in a disk drive D, and other strips D3, D4, D5 stored respectively in the disk drives A, B, D while their corresponding second parity P2 is stored in the disk drive C. In this way, the data is divided and arranged sequentially in each disk drive. Because the RAID level 5 only stores one parity, only one of the user data disks is allowed to have errors at the same time. The user data in the user data disk having errors can be recovered by using the corresponding P value and the other corresponding user data stored in the other normal user data disks to do the XOR operations. For example, if there are errors in D1, then D1 can be recovered by the following formula:D1=D0+D2+ . . . +Dn−1+P  (1′)
In the formula above, “+” also stands for the XOR operation.
Referring to FIG. 4 again, one example is that a disk drive C′ can replace the original disk drive C if there is any damage or error happened in the disk drive C. By then, the data in the disk drive C′ can be rebuilt by the disk drives A, B, D. For example, the strip D2 in the disk drive C′ is produced by performing XOR operations on the strip D0 of the disk drive A, the strip D1 of the disk drive B and the strip P1 of the disk drive D. Therefore, a high fault tolerance and a high data access rate of the disk array can be achieved.
The fault tolerance capability of a hard disk drive becomes more important as the data capacity becomes larger and the reliability requirement becomes higher. A disk array of RAID level 6 (RAID-6) is an extended technology from the RAID level 5. This type of RAID systems is usually set up by using the “Reed-Solomon Codes” that relates to the technology of two or more parities. While storing data, a plurality of disk drives are used for storing multiple parities in order to deal with the situation of having a plurality of damaged or destroyed disk drives at the same time.
Taking a RAID-6 system having two sets of parities as an example, assuming that the RAID system has n number of user data disks D0 to Dn−1 and two parity disks P, Q for storing parities, where the P value is obtained by performing XOR operations on the corresponding user data stored in the user data disks according to Eq. (1) while the Q value can be computed by the following formula:Q=g0*D0+g1*D1+g2*D2+ . . . +gn−1*Dn−1  (2)
If there are two data disks Dx, Dy damaged, through an appropriate derivation one obtains:Dx=A·(P+Pxy)+B·(Q+Qxy)  (3)Dy=(P+Pxy)+Dx  (4)
Wherein, A and B are the constants only related to x and y:A=gy−x·(gy−x+1)−1  (5)B=g−x·(gy−x+1)−1  (6)
Moreover, Pxy and Qxy are the P value and Q value, respectively, when Dx and Dy are zero, namely:Pxy+Dx+Dy=P  (7)Qxy+gx·Dx+gy·Dy=Q  (8)
The algebraic operations in Eqs. (2) to (8), only the power of “y−x” is a normal subtraction operation, and the rest are Galois field algebraic operations, where “+” stands for an XOR operation and “*” for a multiplication-operation. Moreover, g is a prime number, preferably equal to 2.
The multiplication operations of the Galois Field are related to its domain of GF(2n). The related definition, features and operation rules are described in the following reference: 1. “The mathematics of RAID6” by H. Peter Anvin; and 2. “A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems” by James S. Plank.
Theoretically, both computing the Q value and recovering the Dx value need a large quantity of Galois Field multiplication operations, especially the operations involving a constant multiplied by many different values. In hardware design, such multiplication operations are usually implemented by shifting digits or looking up a log table and an inverse log table. It consumes lots of system processing time. Thus, how to simplify and speed up the operations of the Q value in a RAID system having multiple parities becomes an important issue for the related industry.